// // 假设二叉树采用二叉链存储结构存储，设计一个算法计算一棵给定二叉树的所有叶子节点个数。
// // 注意：本题是所有叶子结点
// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// //自定义类型
// typedef int ElemData;
//
// //自定义树节点
// typedef struct TreeNode {
//     ElemData data;
//     struct TreeNode* left;
//     struct TreeNode* right;
// }TreeNode;
//
// //创建树节点
// TreeNode* CreateTreeNode(ElemData x) {
//     TreeNode* newNode=(TreeNode*)malloc(sizeof(TreeNode));
//     if(newNode==NULL) {
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->left=newNode->right=NULL;
//     return newNode;
// }
//
// //插入树节点(二叉搜索树规则:注意)
// TreeNode* InsertTreeNode(TreeNode* root,ElemData x) {
//     if(root==NULL) {
//         return CreateTreeNode(x);
//     }
//     if(x<root->data) {
//         root->left=InsertTreeNode(root->left,x);
//     }else {
//         root->right=InsertTreeNode(root->right,x);
//     }
//     return root;
// }
//
// //计算所有叶子节点个数
// int Compute(TreeNode* root) {
//     if(root==NULL) {
//         return 0;
//     }else if(root->left==NULL&&root->right==NULL) {
//         return 1;
//     }else {
//         return Compute(root->left)+Compute(root->right);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int n = sizeof(values) / sizeof(values[0]);
//     for(int i=0;i<n;i++) {
//         root=InsertTreeNode(root,values[i]);
//     }
//     printf("叶子节点数：%d",Compute(root));
//     free(root);
//     root=NULL;
//     return 0;
// }
//
// // 示例代码的递归调用过程
// // 假设输入的二叉树如下：
// // 复制
// //         50
// //        /  \
// //      30    70
// //     /  \  /  \
// //   20  40 60  80
// // 调用 Compute(root) 的过程如下：
// // 调用 Compute(50)：
// // 调用 Compute(30) 和 Compute(70)。
// // 调用 Compute(30)：
// // 调用 Compute(20) 和 Compute(40)。
// // 调用 Compute(20)：
// // 返回1（叶子节点）。
// // 调用 Compute(40)：
// // 返回1（叶子节点）。
// // 返回 1 + 1 = 2（Compute(30) 的结果）。
// // 调用 Compute(70)：
// // 调用 Compute(60) 和 Compute(80)。
// // 调用 Compute(60)：
// // 返回1（叶子节点）。
// // 调用 Compute(80)：
// // 返回1（叶子节点）。
// // 返回 1 + 1 = 2（Compute(70) 的结果）。
// // 返回 2 + 2 = 4（Compute(50) 的结果）。
// // 总结
// // 递归的底层原理是通过函数调用栈来保存和恢复函数的状态，逐步解决子问题，
// // 并将子问题的解合并起来得到原问题的解。在计算叶子节点数的例子中，递归函数通过分解问题、调用自身、合并结果来实现这一过程。